package _前缀和;

import java.util.*;

/**
 * @Author: 吕庆龙
 * @Date: 2020/8/9 17:00
 * <p>
 * 功能描述:
 */
public class _5471 {

    public static void main(String[] args) {
        int[] nums = new int[]{-1, 3, 5, 1, 4, 2, -9};
        maxNonOverlapping2(nums, 6);

    }

    /**
     * liweiwei的代码
     */
    public static int maxNonOverlapping(int[] nums, int target) {
        // 第 1 步：构造前缀和数组，以便快速计算区间和
        int len = nums.length;
        int[] preSum = new int[len + 1];
        preSum[0] = 0;
        // 意义：preSum[i] 表示下标 i 之前(不包括i)的元素之和
        for (int i = 0; i < len; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }

        // 在当前下标的左边，与当前前缀和相差为 target 的下标
        int[] left = new int[len + 1];
        Arrays.fill(left, Integer.MAX_VALUE);

        // last这个map结构表示：key:为某和时，value:是第几个数(不是索引)
        Map<Integer, Integer> last = new HashMap<>();
        last.put(0, 0);

        // 注意：下面所有的 i 的部分都看为 i + 1
        for (int i = 0; i < len; i++) {
            // 常见操作：last.containsKey(preSum[i + 1] - target)
            //前缀和与target相减，如果在map里，说明这段区间和等于target
            if (last.containsKey(preSum[i + 1] - target)) {
                left[i + 1] = last.get(preSum[i + 1] - target);
            }
            last.put(preSum[i + 1], i + 1);
        }

        // 利用 left 数组找到最大值
        // dp[i] 到i为止不重复子字符的最大数量
        int[] dp = new int[len + 1];
        for (int i = 0; i < len; i++) {
            dp[i + 1] = Math.max(dp[i], dp[i + 1]);
            if (left[i + 1] < i + 1) {
                dp[i + 1] = Math.max(dp[i + 1], dp[left[i + 1]] + 1);
            }
        }
        return dp[len];
    }

    /**
     * https://leetcode-cn.com/problems/maximum-number-of-non-overlapping-subarrays-with-sum-equals-target/solution/qian-zhui-he-java-by-hapibao/
     */
    public static int maxNonOverlapping1(int[] nums, int target) {
        int sum = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        int count = 0;
        map.put(0, 1);
        for (int num : nums) {
            sum += num;
            if (map.containsKey(sum - target)) {
                count++;
                sum = 0;
                map = new HashMap<>();
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }

    //李家辉代码
    public static int maxNonOverlapping2(int[] nums, int target) {
        List<int[]> list = new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();
        int sum = 0;
        map.put(0, -1);
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (map.containsKey(sum - target)) {
                System.out.println(map.get(sum - target) + 1 + "," + i);
                list.add(new int[]{map.get(sum - target) + 1, i});
            }
            map.put(sum, i);
        }
        System.out.println(list.size());
        Collections.sort(list, (a, b) -> {
            if (a[1] == b[1]) {
                return b[0] - a[0];
            } else return a[1] - b[1];
        });
        int left = -1;
        int right = -1;
        int count = 0;
        for (int[] arr : list) {
            if (left == -1) {
                left = arr[0];
                right = arr[1];
                count++;
            } else {
                if (arr[0] > right) {
                    count++;
                    left = arr[0];
                    right = arr[1];
                }
            }
        }
        return count;
    }
}
